package main.Q901_1000;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

public class Q991_1000 {
	public static void main(String[] args) {
		System.out.println("Question991：");
		System.out.println("Question992：");
		System.out.println("Question993：");
		System.out.println("Question994：腐烂的橘子");
		System.out.println("Question995：");
		System.out.println("Question996：");
		System.out.println("Question997：找到小镇法官");
		System.out.println("Question998：");
		System.out.println("Question999：可以被一步捕获的棋子数");
		System.out.println("Question1000：");
	}
}

class Question994 {
	int[] dr = new int[]{-1, 0, 1, 0};
	int[] dc = new int[]{0, -1, 0, 1};

	public int orangesRotting(int[][] grid) {
		int R = grid.length, C = grid[0].length;
		Queue<Integer> queue = new ArrayDeque<Integer>();
		Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
		for (int r = 0; r < R; ++r) {
			for (int c = 0; c < C; ++c) {
				if (grid[r][c] == 2) {
					int code = r * C + c;
					queue.add(code);
					depth.put(code, 0);
				}
			}
		}
		int ans = 0;
		while (!queue.isEmpty()) {
			int code = queue.remove();
			int r = code / C, c = code % C;
			for (int k = 0; k < 4; ++k) {
				int nr = r + dr[k];
				int nc = c + dc[k];
				if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
					grid[nr][nc] = 2;
					int ncode = nr * C + nc;
					queue.add(ncode);
					depth.put(ncode, depth.get(code) + 1);
					ans = depth.get(ncode);
				}
			}
		}
		for (int[] row : grid) {
			for (int v : row) {
				if (v == 1) {
					return -1;
				}
			}
		}
		return ans;
	}
}

class Question997 {
	public int findJudge(int n, int[][] trust) {
		int[] trusts = new int[n + 1], count = new int[n + 1];
		for (int[] person : trust) {
			trusts[person[1]]++;//当前人信任的人
			count[person[0]]++;//当前人信任多少人
		}
		for (int i = 1; i <= n; i++) {
			if (trusts[i] == n - 1 && count[i] == 0) return i;
		}
		return -1;
	}
}

class Question999 {
	public int numRookCaptures(char[][] board) {
		int count = 0;
		int x = -1, y = -1;
		boolean flag = false;
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == 'R') {
					x = i;
					y = j;
					flag = true;
					break;
				}
			}
			if (flag) break;
		}
		//向左
		for (int i = y; i >= 0; i--) {
			if (board[x][i] == 'B') break;
			if (board[x][i] == 'p') {
				count++;
				break;
			}
		}
		//向右
		for (int i = y; i < board[0].length; i++) {
			if (board[x][i] == 'B') break;
			if (board[x][i] == 'p') {
				count++;
				break;
			}
		}
		//向上
		for (int i = x; i >= 0; i--) {
			if (board[i][y] == 'B') break;
			if (board[i][y] == 'p') {
				count++;
				break;
			}
		}
		//向下
		for (int i = x; i < board.length; i++) {
			if (board[i][y] == 'B') break;
			if (board[i][y] == 'p') {
				count++;
				break;
			}
		}
		return count;
	}
}